package E_2024;

import java.util.Collections;
import java.util.Stack;

public class E_100_2 {
    /*
    向一个空栈压入正整数，每当压入一个整数时，执行以下规则(设: 栈顶至栈底整数依次编号为n1、n2...nx， n1为最新压入的整数)
    1.如果n1=n2，则n1、n2全部出栈，压入新数据m(m=2*n1)
    2.如果n1=n2+...+ny(y的范围为[3,x]) ，则n1、n2...ny全部出栈，压入新数据m(m=2*n1)。
    3.如果上述规则都不满足，则不做操作
    如: 依次向栈压入6、1、2、3，当压入2时，栈顶至栈底依次为[2、1、6];当压入3时，3=2+1，3、2、1全部出栈，重新入栈整数6，此时栈顶至栈底依次为[6、6]; 6=6，两个6全部出栈，压入12，最终栈中只剩个元素12。
    向栈中输入一串数字，请输出应用此规则后栈中最终存留的数字。
    输入描述:
        使用单个空格隔开的正整数的字符串，如”5 6 7 8″， 左边的数字先入栈，输入的正整数个数为 x， 1<=x<=1000。
    输出描述:
        最终栈中存留的
     */
    public static void main(String[] args) {
        ans1(new int[]{6,1,1,1,1,1,1,3});
        ans1(new int[]{6,1,1,1,1,1,1,1,1});
        ans1(new int[]{6,1,1,1,1,1,3});
        ans1(new int[]{6,1,2,3});
    }
    public static void ans1(int[] nums){
        Stack<Integer> stack = new Stack<>();
        stack.add(nums[0]);
        for (int i = 1; i < nums.length; i++) {
            int num = nums[i];
            // 判断当前值是否比栈顶值大，若大说明栈内可能存在若干值的和等于当前值
            if (num >= stack.peek()){
                int sum = 0;
                // 存放临时值
                Stack<Integer> temp = new Stack<>();
                while(sum < num && !stack.isEmpty()){
                    Integer pop = stack.pop();
                    sum += pop;
                    if (sum == num){
                        num += sum;
                        sum = 0;
                        temp.clear();
                    }else
                        temp.add(pop);
                }
                // 若临时栈中有值时需还原
                if (!temp.isEmpty()){
                    Collections.reverse(temp);
                    stack.addAll(temp);
                }
            }
            stack.add(num);
        }
        System.out.println(stack);
    }
}
